#include <iostream>
#include <climits>
#include <LEDA/graphics/graphwin.h>
#include <LEDA/graphics/color.h>
#include <LEDA/system/basic.h>
#include "control.h"

#include <LEDA/core/queue.h>
#include <LEDA/core/tuple.h>



using namespace leda;

// Parameters:
//	  queue<two_tuple<node,int> > &q: reference to the queue of tuple of node and depth that have not been visited yet
//    parent: Knoten, von dem aus der aktuelle Knoten besucht wird
//            (parent == v, falls der aktuelle Knoten der Startknoten ist)
//    g: zu durchsuchender Graph (als Referenz)
//    gw: Darstellungsfenster des Graphen (als Referenz)
//    bfsnum: Feld zur Zuordnung von BFS-Nummern zu Knoten (als Referenz)
//    akt: n�chste freie Nummer (als Referenz)
void bfs(queue<two_tuple<node,int> > &q, node &parent, graph &g, GraphWin &gw,
		node_array<int> &bfsnum, node_array<int> &marker, int &akt)
{
	int depth;
	node v;
    edge e;

	if(q.empty()){
		return;
	}

	//our new current node and depth
	two_tuple<node,int> tuple = q.pop();
	v = tuple.first();
	depth = tuple.second();
    bfsnum[v] = akt++;                              // BFS-Nummer zuweisen
    gw.set_user_label(v, string("%d", depth));  	// Tiefe anzeigen
    gw.set_color(v, blue);                           // Knoten rot f�rben
    gw.redraw();                                    // Darstellung aktualisieren
    control_wait(0.5);                              // 0.5 sec warten

    forall_inout_edges(e, v) {  // alle Nachbarkanten von v
        node w = g.opposite(v, e); // Knoten am anderen Ende von e
        if (w != parent) {     // die Kante zum parent ignorieren wir
            if (marker[w] < 0 && bfsnum[w] < 0) { // falls Knoten w noch nicht besucht
            	//appending next reachable adjacent node, and incrementing depth
            	two_tuple<node,int>* t = new two_tuple<node,int>(w,(depth + 1));
            	q.append(*t);

            	marker[w] = 1; // node visited

                gw.set_color(w, green);
                gw.set_width(e, 3);
                gw.set_color(e, blue);

                control_wait(0.5);
            } else {    // Knoten w war schon besucht
                if (bfsnum[w] < bfsnum[v]) { // R�ckw�rtskante
                    control_wait(0.5);         // 0.5 sec warten
                }
                if (marker[w] == 1){
                	gw.set_color(e, red);
                }
            }
        }
    }

    gw.set_color(v, blue); // Knoten blau f�rben

    marker[v] = 2; //mark as inactive

    gw.redraw(); // Darstellung aktualisieren (zur Sicherheit)

    bfs(q, v, g, gw, bfsnum,marker, akt); // recursive call for new q
}


int main(int argc, char *argv[]) {

    GraphWin gw(800, 600);
    gw.display();
    create_control();
    gw.set_directed(false);
    if (argc > 1)
        gw.read(argv[1]);
    gw.edit();
    graph &g = gw.get_graph();

    if (g.number_of_nodes() == 0) {  // Ende, wenn der Graph leer ist.
        gw.close(); destroy_control();
        exit(1);
    }


    /* Variables */
    node_array<int> bfsnum(g, -1);
    node_array<int> marker(g, -1);
    node v;
    edge e;
    int akt = 0;


    forall_nodes(v, g) {
        gw.set_label_type(v, user_label);
        gw.set_user_label(v, string("%d", bfsnum[v])); // Set all the unvisited nodes to -1
        gw.set_color(v, grey3); // Set all the nodes color
    }
    forall_edges(e, g)
    {
        gw.set_color(e, grey3); // Set all the edges
    }

    do {
        while ((v = gw.read_node()) == NULL || bfsnum[v] >= 0); // User selects with mouse the starting node

        //make queue of tuples of node and depth for BFS, and initialize it using the user selected node
        queue<two_tuple<node,int> >* q = new queue<two_tuple<node,int> >();
        two_tuple<node,int>* t = new two_tuple<node,int>(v,0);
        q->append(*t);

        bfs(*q, v, g, gw, bfsnum, marker, akt); // Calling the recursive bfs function
    } while (akt < g.number_of_nodes()); // loop ends when all the nodes where visited



    gw.acknowledge("Ready!");
    gw.edit();
    gw.close();
    destroy_control();
    exit(0);
}
